package org.example.myleet.difficult;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;
import org.example.myleet.Utils.TreeNode;

import java.util.*;

public class DifficultSolution {

    /**
     * 212【字典树+DFS回溯】单词搜索 II
     */
    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public List<String> findWords(char[][] board, String[] words) {
        Trie212[] roots = initTrie(words);
        List<String> result = new ArrayList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int row = 0; row < board.length; ++row) {
            for (int col = 0; col < board[0].length; ++col) {
                //针对整个board的每一个位置进行DFS回溯搜索
                backTrack212(result, board, visited, row, col, roots, new StringBuilder());
            }
        }
        return result;
    }
    /**
     * DFS+回溯
     */
    private void backTrack212(List<String> result, char[][] board, boolean[][] visited, int row, int col, Trie212[] cur, StringBuilder wordBuilder) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            //越界
            return;
        }
        if (visited[row][col]) {
            //在DFS的一次深入搜索中已经访问过了
            return;
        }
        char c = board[row][col];
        int idx = c - 'a';
        if (cur[idx] == null) {
            //字典树中没有对应的单词记录，剪枝
            return;
        }
        //延伸搜索到的单词
        wordBuilder.append(c);
        if (!cur[idx].isFound() && cur[idx].isEnd()) {
            //如果单词是第一次被搜索到的，并且到达单词结尾，则加入到答案中
            result.add(wordBuilder.toString());
            cur[idx].found = true;
        }
        if (isAllEmpty(cur[idx].getChildren())) {
            //搜索到达最长的单词结尾，没有子节点，则可以移除这个单词在字典树中的记录，进行更多剪枝
            cur[idx] = null;
        }
        //标记为已经访问过
        visited[row][col] = true;
        for (int[] direction : DIRECTIONS) {
            if (cur[idx] != null) {
                //DFS继续向4个方向深入搜索
                backTrack212(result, board, visited, row + direction[0], col + direction[1], cur[idx].getChildren(), wordBuilder);
            }
        }
        //回溯
        wordBuilder.deleteCharAt(wordBuilder.length() - 1);
        visited[row][col] = false;
    }
    /**
     * 初始化字典树
     */
    private Trie212[] initTrie(String[] words) {
        Trie212[] roots = new Trie212[26];
        for (String word : words) {
            Trie212[] cur = roots;
            for (int i = 0; i < word.length(); ++i) {
                char c = word.charAt(i);
                int idx = c - 'a';
                if (cur[idx] == null) {
                    cur[idx] = new Trie212();
                    cur[idx].setC(c);
                }
                if (cur[idx].getChildren() == null) {
                    cur[idx].setChildren(new Trie212[26]);
                }
                if (i == word.length() - 1) {
                    cur[idx].setEnd(true);
                }
                cur = cur[idx].getChildren();
            }
        }
        return roots;
    }
    /**
     * 判断字典树的子节点是不是全空，用于删除判断
     */
    private boolean isAllEmpty(Trie212[] children) {
        for (Trie212 child : children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }
    /**
     * 字典树
     */
    static class Trie212 {
        boolean found;
        boolean end;
        char c;
        Trie212[] children;

        public boolean isFound() {
            return found;
        }

        public void setFound(boolean found) {
            this.found = found;
        }

        public boolean isEnd() {
            return end;
        }

        public void setEnd(boolean end) {
            this.end = end;
        }

        public char getC() {
            return c;
        }

        public void setC(char c) {
            this.c = c;
        }

        public Trie212[] getChildren() {
            return children;
        }

        public void setChildren(Trie212[] children) {
            this.children = children;
        }
    }

    /**
     * 321【贪心+单调栈】拼接最大数
     * 40 ms
     */
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] merged, victory = new int[0];
        for (int i = 0; i <= k; i++) {
            if (i > nums1.length || k - i > nums2.length) {
                //不满足条件的情况跳过
                continue;
            }
            //分别求出两个数组使用不同长度的情况下的最大子序列，融合后与最大的结果做比较，胜出保留
            merged = maxMerge(biggestSubSeq(nums1, i), biggestSubSeq(nums2, k - i));
            if (compareNumArr(merged, victory) > 0) {
                victory = merged;
            }
        }
        return victory;
    }
    /**
     * 比较两个结果每一位的大小，以此知道结果哪个大
     */
    public int compareNumArr(int[] a, int[] b) {
        if (a.length > b.length) {
            return 1;
        } else if (a.length < b.length) {
            return -1;
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i] > b[i]) {
                return 1;
            } else if (a[i] < b[i]) {
                return -1;
            }
        }
        return 0;
    }
    /**
     * 最大化融合两个数组成为一个新数组
     */
    public int[] maxMerge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int ai = 0, bi = 0, ri = 0;
        while (ai < a.length || bi < b.length) {
            if (ai > a.length - 1) {
                //a已经到结尾了，只要按顺序接b的元素
                result[ri++] = b[bi++];
            } else if (bi > b.length - 1) {
                //b已经到结尾了，只要按顺序接a的元素
                result[ri++] = a[ai++];
            } else {
                //还没到结尾，
                int i = ai, j = bi;
                while (i < a.length && j < b.length && a[i] == b[j]) {
                    //相等的情况下一直往后查找
                    ++i;
                    ++j;
                }
                if (i == a.length) {
                    //a已经搜到结尾，仍然和b的索引位置相同，就接b的元素
                    result[ri++] = b[bi++];
                } else {
                    if (j == b.length) {
                        //b已经搜到结尾，仍然和a的索引位置相同，但a仍然未完结，就接a的元素
                        result[ri++] = a[ai++];
                    } else {
                        //都还没到结尾，出现不同的数，取大的那个接上正在游走的索引
                        result[ri++] = a[i] > b[j] ? a[ai++] : b[bi++];
                    }
                }
            }
        }
        return result;
    }
    /**
     * 寻找num数组中长度为l的最大子序列，即维护一个不断递减的栈
     */
    public int[] biggestSubSeq(int[] num, int l) {
        if (l == 0) {
            return new int[0];
        }
        if (l >= num.length) {
            return num;
        }
        Deque<Integer> stack = new LinkedList<>();
        //记录还有多少次可以弹出，因为最终结果不能小于长度l
        int availablePop = num.length - l;
        for (int i = 0; i < num.length; i++) {
            while (availablePop > 0 && !stack.isEmpty() && stack.peek() < num[i]) {
                //遇到大于栈顶的数则弹出进行替换
                --availablePop;
                stack.pop();
            }
            //压入当前值，替换刚才从栈顶弹出的数
            stack.push(num[i]);
        }
        while (stack.size() > l) {
            //对超出l长度的部分弹出进行截断
            stack.pop();
        }
        //逆序输出栈就是l长度的最大子序列
        int[] result = new int[l];
        int idx = result.length - 1;
        while (!stack.isEmpty()) {
            result[idx] = stack.pop();
            --idx;
        }
        return result;
    }

    //p1000
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + stones[i];
        }
        int[][][] dp = new int[n][n][k + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int x = 0; x <= k; ++x) {
                    dp[i][j][x] = Integer.MAX_VALUE;
                }
            }
        }
        int r = mergeDfs1000(preSum, k, 0, n - 1, 1, dp);
        return r;
    }
    private int mergeDfs1000(int[] preSum, int k, int l, int r, int p, int[][][] dp) {
        if (dp[l][r][p] < Integer.MAX_VALUE) return dp[l][r][p];
        //l-区间左边界，r-区间右边界，p-分成的堆数
        if (p == 1) {
            if (l == r) {
                dp[l][r][p] = 0;
                return 0;
            }
            dp[l][r][p] = mergeDfs1000(preSum, k, l, r, k, dp) + (preSum[r + 1] - preSum[l]);
            return dp[l][r][p];
        }
        int result = Integer.MAX_VALUE;
        for (int m = l; m < r; m += k - 1) {
            int bestMergeResult = mergeDfs1000(preSum, k, l, m, 1, dp) + mergeDfs1000(preSum, k, m + 1, r, p - 1, dp);
            result = Math.min(result, bestMergeResult);
        }
        dp[l][r][p] = result;
        return result;
    }

    /**
     * 987【DFS+哈希表+优先队列】二叉树的垂序遍历
     */
    private int minCol;
    private int maxCol;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        minCol = 0;
        maxCol = 0;
        Map<Integer, PriorityQueue<int[]>> colNodesMap = new HashMap<>();
        dfs987(root, colNodesMap, 0, 0);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = minCol; i <= maxCol; ++i) {
            PriorityQueue<int[]> nodes = colNodesMap.getOrDefault(i, null);
            if (nodes != null) {
                List<Integer> column = new ArrayList<>();
                while (!nodes.isEmpty()) {
                    column.add(nodes.poll()[0]);
                }
                result.add(column);
            }
        }
        return result;
    }
    private void dfs987(TreeNode treeNode, Map<Integer, PriorityQueue<int[]>> colNodesMap, int row, int col) {
        //DFS先序遍历，同时记录node的row和col，一边加入到优先队列中，一边记录其col
        minCol = Math.min(minCol, col);
        maxCol = Math.max(maxCol, col);
        //value, row, col
        PriorityQueue<int[]> nodes = colNodesMap.getOrDefault(col, new PriorityQueue<>((o1, o2) -> {
            if (o1[1] != o2[1]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        }));
        nodes.offer(new int[]{treeNode.val, row, col});
        colNodesMap.put(col, nodes);
        if (treeNode.left != null) {
            dfs987(treeNode.left, colNodesMap, row + 1, col - 1);
        }
        if (treeNode.right != null) {
            dfs987(treeNode.right, colNodesMap, row + 1, col +1);
        }
    }

    //1096
    public List<String> braceExpansionII(String expression) {
        //栈记录最新收到的字符串集合
        Deque<Set<String>> stack = new LinkedList<>();
        Set<String> set = new HashSet<>();
        stack.push(set);
        int i = 0;
        while (i < expression.length()) {
            char ch = expression.charAt(i);
            if (ch == ',') {
                //完成一个字符串集合的解析，入栈一个新的空集合
                set = new HashSet<>();
                stack.push(set);
            } else if (ch == '{') {
                //遇到左花括号，需要找到对应的右花括号
                StringBuilder sb = new StringBuilder();
                int level = 1;
                while (true) {
                    ++i;
                    if (i >= expression.length()) break;
                    ch = expression.charAt(i);
                    if (ch == '{') ++level;
                    else if (ch == '}') --level;
                    if (level < 1) {
                        break;
                    }
                    sb.append(ch);
                }
                //找到完整的花括号内的表达式，递归解释
                List<String> r = braceExpansionII(sb.toString());
                //取出栈顶缓存的字符串集，做笛卡尔积，结果继续放在栈顶缓存
                set = stack.pop();
                if (set.size() < 1) set.addAll(r);
                else {
                    Set<String> newSet = new HashSet<>(set.size() * r.size());
                    for (String a : set) {
                        for (String b : r) {
                            newSet.add(a + b);
                        }
                    }
                    set = newSet;
                }
                stack.push(set);
            } else {
                //剩下一种情况就是一个元素，则找出这个完整的元素
                StringBuilder sb = new StringBuilder();
                sb.append(ch);
                ++i;
                while (i < expression.length() && Character.isAlphabetic(ch = expression.charAt(i))) {
                    sb.append(ch);
                    ++i;
                }
                //取出栈顶缓存的字符串集，做笛卡尔积，结果继续放在栈顶缓存
                set = stack.pop();
                String b = sb.toString();
                if (set.size() < 1) set.add(b);
                else {
                    Set<String> newSet = new HashSet<>(set.size());
                    for (String a : set) {
                        newSet.add(a + b);
                    }
                    set = newSet;
                }
                stack.push(set);
                --i;
            }
            ++i;
        }
        //取出所有的字符串集合取并集，并排序
        Set<String> result = new HashSet<>();
        while (!stack.isEmpty()) {
            result.addAll(stack.pop());
        }
        List<String> answer = new ArrayList<>(result);
        answer.sort(Comparator.naturalOrder());
        return answer;
    }

    //1147
    public int longestDecomposition(String text) {
        int n;
        if (null == text || (n = text.length()) == 0) return 0;
        if (n == 1) return 1;
        int k = 1, l = 0, r = 0;
        char a = text.charAt(0);
        for (int i = n - 1; i >= n / 2; --i) {
            char b = text.charAt(i);
            if (b == a) {
                l = 0;
                r = i;
                boolean identical = true;
                while (r < n) {
                    if (text.charAt(l) != text.charAt(r)) {
                        identical = false;
                        break;
                    }
                    ++l;
                    ++r;
                }
                if (identical) {
                    ++k;
                    break;
                }
            }
        }
        if (k == 2) {
            return k + longestDecomposition(text.substring(l, n - l));
        }
        return k;
    }

    //p1172
    static class PlateStack {
        int i;
        int size;
        Deque<Integer> values;
        public PlateStack(int i, int size) {
            this.i = i;
            this.size = size;
            values = new LinkedList<>();
        }
        public boolean isFull() {
            return values.size() >= size;
        }
        public boolean isEmpty() {
            return values.isEmpty();
        }
        public void pushVal(int v) {
            values.push(v);
        }
    }
    static class DinnerPlates {
        int capacity;
        List<PlateStack> stacks;
        PriorityQueue<PlateStack> pushAscHeap;
        Set<Integer> canPushStackSet;
        PriorityQueue<PlateStack> popDescHeap;
        Set<Integer> canPopStackSet;
        public DinnerPlates(int capacity) {
            this.capacity = capacity;
            stacks = new ArrayList<>();
            //维护所有非满的栈，按id从小到大排列，并记录已经在堆中的栈id
            pushAscHeap = new PriorityQueue<>((Comparator.comparingInt(o -> o.i)));
            canPushStackSet = new HashSet<>();
            //维护所有非空的栈，按id从大到小排列，并记录已经在堆中的栈id
            popDescHeap = new PriorityQueue<>((o1, o2) -> o2.i - o1.i);
            canPopStackSet = new HashSet<>();
        }
        public void push(int val) {
            PlateStack stack;
            if (pushAscHeap.isEmpty()) {
                //没有非满栈的情况下，说明所有的栈都满了，新建一个栈来存放新的val
                stack = new PlateStack(stacks.size(), capacity);
                stacks.add(stack);
            } else {
                //取出一个可以插入val的栈
                stack = pushAscHeap.poll();
                canPushStackSet.remove(stack.i);
            }
            stack.pushVal(val);
            if (!stack.isFull()) {
                //如果栈未满，继续维护到非满栈的堆中
                pushAscHeap.offer(stack);
                canPushStackSet.add(stack.i);
            }
            if (!canPopStackSet.contains(stack.i)) {
                //如果非空栈堆中没有这个栈，也放到非空栈堆中，一遍快速找到可以用于pop的栈
                popDescHeap.offer(stack);
                canPopStackSet.add(stack.i);
            }
        }
        public int pop() {
            //如果没有非空的栈，不能pop，返回-1
            if (popDescHeap.isEmpty()) return -1;
            //从右到左扫描直到找到非空的栈
            PlateStack stack = popDescHeap.poll();
            canPopStackSet.remove(stack.i);
            while (stack.isEmpty()) {
                stack = popDescHeap.poll();
                if (null != stack) {
                    canPopStackSet.remove(stack.i);
                } else break;
            }
            //如果没有非空的栈，不能pop，返回-1
            if (null == stack) return -1;
            //弹出一个值用于返回
            int v = stack.values.pop();
            if (!canPushStackSet.contains(stack.i)) {
                //刚刚弹出值的栈有位置了，非满，如果这个栈不在非满栈堆中，维护之
                pushAscHeap.offer(stack);
                canPushStackSet.add(stack.i);
            }
            if (!stack.isEmpty()) {
                //如果这个栈还未空，继续维护在非空栈堆中
                popDescHeap.offer(stack);
                canPopStackSet.add(stack.i);
            }
            return v;
        }
        public int popAtStack(int index) {
            if (index > stacks.size() - 1) return -1;
            PlateStack stack = stacks.get(index);
            if (!canPushStackSet.contains(stack.i)) {
                //由于弹出了值，有位置了，非满，如果这个栈不在非满栈堆中，维护之
                pushAscHeap.offer(stack);
                canPushStackSet.add(stack.i);
            }
            //如果这个栈其实是空的，则也没有值弹出
            if (stack.isEmpty()) return -1;
            return stack.values.pop();
        }
    }

    //1187
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        Set<Integer> set = new HashSet<>(arr2.length);
        for (int num : arr2) {
            set.add(num);
        }
        List<Integer> list = new ArrayList<>(set);
        list.sort(Comparator.naturalOrder());
        arr2 = new int[list.size()];
        int k = 0;
        for (Integer integer : list) {
            arr2[k] = integer;
            ++k;
        }
        int n = arr1.length, m = arr2.length;
        //dp[i][j] for the min element of i when i for index in arr1 and j for the replacing count, note i >= j + 1
        int MAX_VALUE = 0x3f3f3f3f;
        int[][] dp = new int[n][m + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                dp[i][j] = MAX_VALUE;
            }
        }
        dp[0][0] = arr1[0];
        dp[0][1] = Math.min(arr1[0], arr2[0]);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (arr1[i] > dp[i - 1][j]) {
                    dp[i][j] = Math.min(dp[i][j], arr1[i]);
                }
                if (j > 0) {
                    int prevMin = dp[i - 1][j - 1];
                    int replacement = binarySearch1187(arr2, prevMin + 1, j - 1);
                    if (replacement >= 0) {
                        dp[i][j] = Math.min(dp[i][j], replacement);
                    }
                }
            }
        }
        for (int j = 0; j <= m; ++j) {
            if (dp[n - 1][j] < MAX_VALUE) {
                return j;
            }
        }
        return -1;
    }
    private int binarySearch1187(int[] arr, int target, int start) {
        int l = start, r = arr.length - 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (arr[m] < target) {
                l = m + 1;
            } else if (target < arr[m]) {
                r = m;
            } else {
                return arr[m];
            }
        }
        if (target <= arr[r]) return arr[r];
        return -1;
    }

    //p1590
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int m = 0;
        for (int num : nums) {
            m = (m + num) % p;
        }
        //直接能够整除，否则不为0的m就是sum%p得到的余数
        if (m == 0) return 0;
        //设nums总和为sum，移除某个数组的和为x，则要求的情况为(sum - x) % p = 0
        //根据同余定理，可以得到sum % p = m = x % p，即需要找到x % p = m
        //利用前缀和的特性，若前缀和数组为s[]，则x = s[j] - s[i]，i < j
        //x % p = m可以转换为(s[j] - s[i]) % p = m，移项得s[j]%p - s[i]%p = m，即求在s[j]%p情况下是否存在s[j]%p - m = s[i]%p
        //当固定s[j]%p时，s[i]%p可以通过哈希表记录知道其是否存在，而s[i]%p如果出现过的话，那么一定是曾经的s[j]%p
        //以下，另y = s[j]%p，x = s[i]%p
        int answer = n, y = 0;
        Map<Integer, Integer> preSumModMapIdx = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            preSumModMapIdx.put(y, i);
            y = (y + nums[i]) % p;
            int x = (y - m + p) % p; //加p是为了防止(y - m) % p为负数
            Integer prevMatchIdx = preSumModMapIdx.get(x);
            if (prevMatchIdx != null) {
                answer = Math.min(answer, i - prevMatchIdx + 1);
            }
        }
        return answer == n ? -1 : answer;
    }

    //p1825
    static class MKAverage {
        private int m;
        private int k;
        private int m2k;
        private int sum;
        private Queue<Integer> queue;
        private PriorityQueue<Integer> smallK; //记录最小的k个数范围
        private PriorityQueue<Integer> bigK; //记录最大的k个数范围
        private TreeMap<Integer, Integer> values; //记录中间的m-2k个数字的桶
        private boolean init;
        public MKAverage(int m, int k) {
            this.m = m;
            this.k = k;
            m2k = m - 2 * k;
            queue = new LinkedList<>();
            sum = 0;
            smallK = new PriorityQueue<>(Comparator.reverseOrder());
            bigK = new PriorityQueue<>(Comparator.naturalOrder());
            values = new TreeMap<>(Comparator.naturalOrder());
            init = false;
        }

        public void addElement(int num) {
            //入队
            queue.offer(num);
            if (init) {
                if (!smallK.isEmpty() && num <= smallK.peek()) {
                    //num处于最小的k个数里面，添加到前k个数中，多出来的一个数挤到中间部分
                    smallK.offer(num);
                    int top = smallK.poll();
                    values.put(top, values.getOrDefault(top, 0) + 1);
                    sum += top;
                } else if (!values.isEmpty() && num <= values.lastKey()) {
                    //num处于中间部分，添加到中间部分，并更新sum
                    values.put(num, values.getOrDefault(num, 0) + 1);
                    sum += num;
                } else {
                    //num处于最大的k个数里面，添加到后k个数中，多出来的一个数挤到中间部分
                    bigK.offer(num);
                    int bottom = bigK.poll();
                    values.put(bottom, values.getOrDefault(bottom, 0) + 1);
                    sum += bottom;
                }
                //出队一个，这个需要删掉的
                int removeV = queue.poll();
                if (removeV <= smallK.peek()) {
                    //在前k个里面，删除
                    smallK.remove(removeV);
                } else if (removeV <= values.lastKey()) {
                    //在中间部分，删除
                    int cnt = values.get(removeV);
                    --cnt;
                    if (cnt <= 0) {
                        values.remove(removeV);
                    } else {
                        values.put(removeV, cnt);
                    }
                    sum -= removeV;
                } else {
                    //在后k个里面，删除
                    bigK.remove(removeV);
                }
                //前面的处理操作都是尽量挤到中间去，此处平衡前k个数和后k个数，不够的话都从中间挪过去
                if (smallK.size() < k) {
                    int bottom = values.firstKey();
                    int cnt = values.get(bottom);
                    --cnt;
                    if (cnt <= 0) {
                        values.remove(bottom);
                    } else {
                        values.put(bottom, cnt);
                    }
                    sum -= bottom;
                    smallK.offer(bottom);
                }
                if (bigK.size() < k) {
                    int top = values.lastKey();
                    int cnt = values.get(top);
                    --cnt;
                    if (cnt <= 0) {
                        values.remove(top);
                    } else {
                        values.put(top, cnt);
                    }
                    sum -= top;
                    bigK.offer(top);
                }
            } else {
                //未初始化，都先放到中间部分
                values.put(num, values.getOrDefault(num, 0) + 1);
                if (queue.size() >= m) {
                    //init，达到m个数，初始化，将前k个数和后k个数放到对应的优先队列中
                    while (smallK.size() < k) {
                        int bottom = values.firstKey();
                        int cnt = values.get(bottom);
                        --cnt;
                        if (cnt <= 0) {
                            values.remove(bottom);
                        } else {
                            values.put(bottom, cnt);
                        }
                        smallK.offer(bottom);
                    }
                    while (bigK.size() < k) {
                        int top = values.lastKey();
                        int cnt = values.get(top);
                        --cnt;
                        if (cnt <= 0) {
                            values.remove(top);
                        } else {
                            values.put(top, cnt);
                        }
                        bigK.offer(top);
                    }
                    //统计中间部分的和sum
                    for (Map.Entry<Integer, Integer> entry : values.entrySet()) {
                        sum += entry.getValue() * entry.getKey();
                    }
                    //完成初始化
                    init = true;
                }
            }
        }

        public int calculateMKAverage() {
            if (init) {
                return sum / m2k;
            }
            return -1;
        }
    }

    //p1092
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; ++j) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    //字符匹配，则无需增加编辑距离
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不匹配，则有3种选择
                    //2. 选用dp[i][j-1]+1，即s[i-1]和t[j-1]不匹配但通过选用s[i]插入、t字符串跳过一个字符匹配（使用"-"表示）
                    //3. 选用dp[i-1][j]+1，即s[i-1]和t[j-1]不匹配但通过选用t[j]插入、s字符串跳过一个字符匹配（使用"-"表示）
                    //从中选一种编辑距离最小的得到dp[i][j]
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1;
                }
            }
        }
        int editDistance = dp[m][n];
        //然后从dp[m][n]位置通过回溯重新构建利用编辑距离重构alignment
        StringBuilder sp = new StringBuilder(2 * m);
        StringBuilder tp = new StringBuilder(2 * n);
        int row = m, col = n;
        while (row > 0 || col > 0) {
            if (row > 0 && col > 0) {
                if (dp[row - 1][col - 1] < dp[row - 1][col] && dp[row - 1][col - 1] < dp[row][col - 1]) {
                    //dp[row-1][col-1]最小，则可能为s[i-1]和t[j-1]匹配得到
                    sp.append(str1.charAt(row - 1));
                    tp.append(str2.charAt(col - 1));
                    --row;
                    --col;
                } else if (dp[row - 1][col] < dp[row][col - 1] && dp[row - 1][col] < dp[row - 1][col - 1]) {
                    //dp[row-1][col]最小，则可能为s[i-1]作为插入，而t的alignment使用"-"进行align
                    sp.append(str1.charAt(row - 1));
                    tp.append('-');
                    --row;
                } else if (dp[row][col - 1] < dp[row - 1][col] && dp[row][col - 1] < dp[row - 1][col - 1]) {
                    //dp[row][col-1]最小，则可能为t[j-1]作为插入，而s的alignment使用"-"进行align
                    sp.append('-');
                    tp.append(str2.charAt(col - 1));
                    --col;
                } else  {
                    if (dp[row - 1][col - 1] == dp[row][col] && (dp[row - 1][col - 1] <= dp[row - 1][col] || dp[row - 1][col - 1] <= dp[row][col - 1])) {
                        //dp[row-1][col-1]和dp[row][col]相等，且dp[row-1][col]和dp[row][col-1]都较大，则可能为s[i-1]和t[j-1]匹配得到
                        sp.append(str1.charAt(row - 1));
                        tp.append(str2.charAt(col - 1));
                        --row;
                        --col;
                    } else if (dp[row - 1][col] < dp[row][col - 1]) {
                        //可能为s[i-1]作为插入，而t的alignment使用"-"进行align
                        sp.append(str1.charAt(row - 1));
                        tp.append('-');
                        --row;
                    } else {
                        //可能为t[j-1]作为插入，而s的alignment使用"-"进行align
                        sp.append('-');
                        tp.append(str2.charAt(col - 1));
                        --col;
                    }
                }
            } else {
                //剩下没有匹配完的则对应使用"-"进行align
                if (row > 0) {
                    sp.append(str1.charAt(row - 1));
                    tp.append('-');
                    --row;
                }
                if (col > 0) {
                    sp.append('-');
                    tp.append(str2.charAt(col - 1));
                    --col;
                }
            }
        }
        //由于回溯是append的方式拼接的，因此要得到正序的结果需要进行reverse
        sp.reverse();
        tp.reverse();
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < sp.length(); ++i) {
            char sc = sp.charAt(i);
            char tc = tp.charAt(i);
            if (sc == '-') {
                result.append(tc);
            } else if (tc == '-') {
                result.append(sc);
            } else {
                result.append(sc);
                if (sc != tc) {
                    result.append(tc);
                }
            }
        }
        return result.toString();
    }

    //p1263
    public int minPushBox(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int sx = -1, sy = -1, bx = -1, by = -1; // 玩家、箱子的初始位置
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                if (grid[x][y] == 'S') {
                    sx = x;
                    sy = y;
                } else if (grid[x][y] == 'B') {
                    bx = x;
                    by = y;
                }
            }
        }

        int[] d = {0, -1, 0, 1, 0};

        int[][] dp = new int[m * n][m * n];
        for (int i = 0; i < m * n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        Queue<int[]> queue = new ArrayDeque<int[]>();
        dp[sx * n + sy][bx * n + by] = 0; // 初始状态的推动次数为 0
        queue.offer(new int[]{sx * n + sy, bx * n + by});
        while (!queue.isEmpty()) {
            Queue<int[]> queue1 = new ArrayDeque<int[]>();
            while (!queue.isEmpty()) {
                int[] arr = queue.poll();
                int s1 = arr[0], b1 = arr[1];
                int sx1 = s1 / n, sy1 = s1 % n, bx1 = b1 / n, by1 = b1 % n;
                if (grid[bx1][by1] == 'T') { // 箱子已被推到目标处
                    return dp[s1][b1];
                }
                for (int i = 0; i < 4; i++) { // 玩家向四个方向移动到另一个状态
                    int sx2 = sx1 + d[i], sy2 = sy1 + d[i + 1], s2 = sx2*n+sy2;
                    if (!ok(grid, m, n, sx2, sy2)) { // 玩家位置不合法
                        continue;
                    }
                    if (bx1 == sx2 && by1 == sy2) { // 推动箱子
                        int bx2 = bx1 + d[i], by2 = by1 + d[i + 1], b2 = bx2*n+by2;
                        if (!ok(grid, m, n, bx2, by2) || dp[s2][b2] <= dp[s1][b1] + 1) { // 箱子位置不合法 或 状态已访问
                            continue;
                        }
                        dp[s2][b2] = dp[s1][b1] + 1;
                        queue1.offer(new int[]{s2, b2});
                    } else {
                        if (dp[s2][b1] <= dp[s1][b1]) { // 状态已访问
                            continue;
                        }
                        dp[s2][b1] = dp[s1][b1];
                        queue.offer(new int[]{s2, b1});
                    }
                }
            }
            queue = queue1;
        }
        return -1;
    }
    public boolean ok(char[][] grid, int m, int n, int x, int y) { // 不越界且不在墙上
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
    }

    //p1289
    public int minFallingPathSum(int[][] grid) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int n = grid.length;
        int[] dp0 = new int[n];
        int[] dp1 = new int[n];
        for (int j = 0; j < n; ++j) {
            dp0[j] = grid[0][j];
            minHeap.offer(grid[0][j]);
        }
        for (int i = 1; i < n; ++i) {
            PriorityQueue<Integer> nextMinHeap = new PriorityQueue<>();
            for (int j = 0; j < n; ++j) {
                Integer buffered = null;
                if (minHeap.peek() == dp0[j]) buffered = minHeap.poll();
                dp1[j] = grid[i][j] + minHeap.peek();
                nextMinHeap.offer(dp1[j]);
                if (null != buffered) minHeap.offer(buffered);
            }
            minHeap = nextMinHeap;
            dp0 = dp1;
            dp1 = new int[n];
        }
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; ++j) {
            minSum = Math.min(minSum, dp0[j]);
        }
        return minSum;
    }
    public int minFallingPathSum2(int[][] grid) {
        int[] min2 = new int[2];
        Arrays.fill(min2, Integer.MAX_VALUE);
        int n = grid.length;
        int[] dp0 = new int[n];
        int[] dp1 = new int[n];
        for (int j = 0; j < n; ++j) {
            dp0[j] = grid[0][j];
            if (min2[0] > grid[0][j]) {
                min2[1] = min2[0];
                min2[0] = grid[0][j];
            } else {
                if (min2[1] > grid[0][j]) {
                    min2[1] = grid[0][j];
                }
            }
        }
        for (int i = 1; i < n; ++i) {
            int[] nextMin2 = new int[2];
            Arrays.fill(nextMin2, Integer.MAX_VALUE);
            for (int j = 0; j < n; ++j) {
                int minSumPrev = min2[0] == dp0[j] ? min2[1] : min2[0];
                dp1[j] = grid[i][j] + minSumPrev;
                if (nextMin2[0] > dp1[j]) {
                    nextMin2[1] = nextMin2[0];
                    nextMin2[0] = dp1[j];
                } else {
                    if (nextMin2[1] > dp1[j]) {
                        nextMin2[1] = dp1[j];
                    }
                }
            }
            min2 = nextMin2;
            dp0 = dp1;
            dp1 = new int[n];
        }
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; ++j) {
            minSum = Math.min(minSum, dp0[j]);
        }
        return minSum;
    }

    //1782【排序+双指针】统计点对的数目
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        int base = 100000;
        Map<Integer, Integer> edgeCnt = new HashMap<>();
        int[] degree = new int[n + 1];
        for (int[] edge : edges) {
            int e1 = Math.min(edge[0], edge[1]);
            int e2 = Math.max(edge[0], edge[1]);
            int e = e1 * base + e2;
            edgeCnt.put(e, edgeCnt.getOrDefault(e, 0) + 1);
            degree[e1]++;
            degree[e2]++;
        }
        int[] degreeSorted = new int[n + 1];
        System.arraycopy(degree, 1, degreeSorted, 1, n);
        Arrays.sort(degreeSorted);
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int total = 0;
            int q = queries[i];
            int left = 1, right = degree.length - 1;
            while (left < right) {
                if (degreeSorted[right] + degreeSorted[left] <= q) {
                    ++left;
                    continue;
                }
                total += right - left;
                --right;
            }
            for (int e : edgeCnt.keySet()) {
                int e1 = e / base;
                int e2 = e % base;
                if (degree[e1] + degree[e2] > q && degree[e1] + degree[e2] - edgeCnt.get(e) <= q) {
                    --total;
                }
            }
            answer[i] = total;
        }
        return answer;
    }

    //p1851
    public int[] minInterval(int[][] intervals, int[] queries) {
        int m = intervals.length;
        int n = queries.length;
        int[] cpQueries = new int[n];
        System.arraycopy(queries, 0, cpQueries, 0, n);
        int[] answer = new int[n];
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        Arrays.sort(cpQueries);
        Map<Integer, Integer> answerMap = new HashMap<>();
        PriorityQueue<int[]> minLenPq = new PriorityQueue<>((o1, o2) -> o1[1] - o1[0] - o2[1] + o2[0]);
        int i = 0;
        for (int j = 0; j < n; ++j) {
            int q = cpQueries[j];
            if (answerMap.containsKey(q)) continue;
            while (i < m && intervals[i][0] <= q) {
                minLenPq.offer(intervals[i++]);
            }
            while (!minLenPq.isEmpty() && minLenPq.peek()[1] < q) {
                minLenPq.poll();
            }
            int answerQ = minLenPq.isEmpty() ? -1 : (minLenPq.peek()[1] - minLenPq.peek()[0] + 1);
            answerMap.put(q, answerQ);
        }
        for (int j = 0; j < n; ++j) {
            answer[j] = answerMap.get(queries[j]);
        }
        return answer;
    }

    //p2106
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int[] startFruit = null;
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + fruits[i][1];
            if (fruits[i][0] == startPos) {
                startFruit = fruits[i];
            }
        }
        if (k == 0) {
            if (null == startFruit) return 0;
            return startFruit[1];
        }
        int answer = 0;
        for (int i = startPos - k; i <= startPos; ++i) {
            int left = i;
            int right = left + (k - (startPos - left));
            right = Math.max(right, startPos);
            int l = binarySearch2106(fruits, left);
            int r = binarySearch2106(fruits, right);
            if (left <= fruits[r][0] && right >= fruits[r][0]) ++r;
            answer = Math.max(answer, preSum[r] - preSum[l]);
        }
        for (int i = startPos + 1; i <= startPos + k; ++i) {
            int right = i;
            int left = right - (k - (right - startPos));
            left = Math.min(left, startPos);
            int l = binarySearch2106(fruits, left);
            int r = binarySearch2106(fruits, right);
            if (left <= fruits[r][0] && right >= fruits[r][0]) ++r;
            answer = Math.max(answer, preSum[r] - preSum[l]);
        }
        return answer;
    }
    private int binarySearch2106(int[][] fruits, int target) {
        int left = 0, right = fruits.length - 1, mid;
        while (left < right) {
            mid = (left + right) >> 1;
            if (fruits[mid][0] < target) {
                left = mid + 1;
            } else if (fruits[mid][0] > target) {
                right = mid;
            } else {
                return mid;
            }
        }
        return left;
    }

    /**
     * 2251【优先队列排序+前缀和+二分查找】花期内花的数目
     */
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int n = flowers.length;
        //计算开花总数的前缀和，需要按顺序计算，所以开花时间先排序，用优先队列排序
        PriorityQueue<Integer> pq = new PriorityQueue<>(n, Comparator.naturalOrder());
        for (int[] flower : flowers) {
            pq.add(flower[0]);
        }
        int bloomTime = pq.poll();
        int bloomCnt = 1;
        //用有序集合记录时间节点的开花总数前缀和
        TreeMap<Integer, Integer> bloomMap = new TreeMap<>();
        bloomMap.put(bloomTime, bloomCnt);
        while (!pq.isEmpty()) {
            bloomTime = pq.poll();
            bloomMap.put(bloomTime, ++bloomCnt);
        }
        //下面收集各时间节点总凋谢数量的前缀和，同样的原理，只不过凋谢时间是flower[1]+1
        for (int[] flower : flowers) {
            pq.add(flower[1] + 1);
        }
        int fadeTime = pq.poll();
        int fadeCnt = 1;
        TreeMap<Integer, Integer> fadeMap = new TreeMap<>();
        fadeMap.put(fadeTime, fadeCnt);
        while (!pq.isEmpty()) {
            fadeTime = pq.poll();
            fadeMap.put(fadeTime, ++fadeCnt);
        }
        //下面利用前缀和结合二分查找计算每个查询结果
        Map<Integer, Integer> existAnswer = new HashMap<>();
        int[] answer = new int[people.length];
        for (int i = 0; i < people.length; ++i) {
            Integer a = existAnswer.get(people[i]);
            if (null != a) {
                answer[i] = a;
                continue;
            }
            //二分查找找出people[i]时间点的总开花数量
            Integer prevKey = bloomMap.floorKey(people[i]);
            if (null == prevKey) {
                answer[i] = 0;
                existAnswer.put(people[i], answer[i]);
                continue;
            }
            bloomCnt = bloomMap.get(prevKey);
            //二分查找找出people[i]时间点的总凋谢数量
            prevKey = fadeMap.floorKey(people[i]);
            if (null == prevKey) {
                answer[i] = bloomCnt;
                existAnswer.put(people[i], answer[i]);
                continue;
            }
            fadeCnt = fadeMap.get(prevKey);
            //当前开花的数量等于总开花数量减总凋谢数量
            answer[i] = bloomCnt - fadeCnt;
            existAnswer.put(people[i], answer[i]);
        }
        return answer;
    }

    /**
     * 2258【BFS+二分查找】逃离火灾
     * 先用BFS刷出火焰到达每个可及位置的最短时间，然后用二分查找逐个值尝试等待时间，每个等待时间进行一次模拟以知道能不能成功
     */
    public int maximumMinutes(int[][] grid) {
        int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int m = grid.length, n = grid[0].length;
        //先找出所有火焰初始位置
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        //然后用BFS刷出每个火焰可及最短时间
        int[][] fireReachTime = new int[m][n];
        int t = 1;
        while (!queue.isEmpty()) {
            int l = queue.size();
            for (int i = 0; i < l; ++i) {
                int[] p = queue.poll();
                for (int[] d : directions) {
                    int r = p[0] + d[0];
                    int c = p[1] + d[1];
                    if (0 <= r && r < m && 0 <= c && c < n && grid[r][c] == 0 && !visited[r][c]) {
                        queue.offer(new int[]{r, c});
                        visited[r][c] = true;
                        fireReachTime[r][c] = t;
                    }
                }
            }
            ++t;
        }
        //找出火焰不可及的地方，把时间设为最大值，代表不可到达
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0 && fireReachTime[i][j] == 0) {
                    fireReachTime[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        //利用二分查找逐个等待时间尝试是否能到达
        int left = 0, right = 1000000000, er = m - 1, ec = n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            boolean canReachSafeHouse = canReachSafe2258(grid, directions, m, n, fireReachTime, er, ec, mid);
            if (canReachSafeHouse) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return canReachSafe2258(grid, directions, m, n, fireReachTime, er, ec, left) ? left : left - 1;
    }
    private static boolean canReachSafe2258(int[][] grid, int[][] directions, int m, int n, int[][] fireReachTime, int er, int ec, int waitTime) {
        //用BFS模拟一次在等待waitTime时间之后是够能够成功到达安全屋
        boolean[][] visited;
        int t = waitTime + 1;
        boolean canReachSafeHouse = false;
        visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        breakTag:
        while (!queue.isEmpty()) {
            int l = queue.size();
            for (int i = 0; i < l; ++i) {
                int[] p = queue.poll();
                for (int[] d : directions) {
                    int r = p[0] + d[0];
                    int c = p[1] + d[1];
                    if (0 <= r && r < m && 0 <= c && c < n && grid[r][c] == 0 && !visited[r][c]) {
                        if (r == er && c == ec) {
                            //如果到达安全屋时刚好火焰到达也算能成功进入
                            canReachSafeHouse = fireReachTime[r][c] >= t;
                            break breakTag;
                        }
                        if (fireReachTime[r][c] > t) {
                            queue.offer(new int[]{r, c});
                            visited[r][c] = true;
                        }
                    }
                }
            }
            ++t;
        }
        return canReachSafeHouse;
    }

    //p2488
    public int countSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] mask = new int[n];
        int preSum = 0;
        Map<Integer, Integer> startMapFreq = new HashMap<>();
        startMapFreq.put(0, 1);
        boolean findK = false;
        int answer = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > k) mask[i] = 1;
            else if (nums[i] < k) mask[i] = -1;
            else {
                mask[i] = 0;
                findK = true;
            }
            int p = preSum + mask[i];
            if (findK) {
                int start0 = startMapFreq.getOrDefault(p, 0);
                int start1 = startMapFreq.getOrDefault(p - 1, 0);
                answer += start0 + start1;
            } else {
                startMapFreq.put(p, startMapFreq.getOrDefault(p, 0) + 1);
            }
            preSum = p;
        }
        return answer;
    }

    //2681
    public int sumOfPower(int[] nums) {
        int MOD = 1000000007;
        int n = nums.length;
        Arrays.sort(nums);
        //代表选取nums[i]作为最大数字时，组合中的最小数字的情况数量
        long[] dp = new long[n];
        //代表dp[0]+dp[1]+...+dp[j]的和，用前缀和存储，用于加速dp[0]+dp[1]+...+dp[j]的求和运算
        long[] preSum = new long[n + 1];
        long answer = 0L;
        for (int i = 0; i < n; ++i) {
            //下一种组合中的最小数字的情况数量状态递推为：上一种组合的最小数字的情况数量之和加上最新数字nums[i]
            dp[i] = preSum[i] + nums[i];
            //下一种组合中的最小数字的情况数量之和递推为：上一种组合的最小数字的情况数量之和加上本组合中的最小数字情况数量
            preSum[i + 1] = preSum[i] + dp[i];
            preSum[i + 1] %= MOD;
            answer += ((((long) nums[i] * nums[i]) % MOD) * dp[i]) % MOD;
            answer %= MOD;
        }
        return (int) answer;
    }

    public static void main(String[] args) {
        DifficultSolution solution = new DifficultSolution();
        Assert.isTrue(0 == solution.maximumMinutes(Parser.parse("[[0,2,0,0,1],[0,2,0,2,2],[0,2,0,0,0],[0,0,2,2,0],[0,0,0,0,0]]")));
        Assert.isTrue(-1 == solution.maximumMinutes(Parser.parse("[[0,1],[0,0]]")));
        Assert.isTrue(1000000000 == solution.maximumMinutes(Parser.parse("[[0,0,0],[2,2,0],[1,2,0]]")));
        Assert.isTrue(3 == solution.maximumMinutes(Parser.parse("[[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]")));
    }
}
